#ifndef BINOMIALHEAP_CPP
#define BINOMIALHEAP_CPP

#include <cstddef>
#include <math.h>
#include <iostream>
#include "Queue.cpp"

using namespace std;

template <class T>
class BinomialHeapNode
{
public:
    //data part
    T* dataLoad;
    unsigned int* key;
    BinomialHeapNode** pointerStore;

    BinomialHeapNode* child;
    BinomialHeapNode* sibling;
    int degree;
    BinomialHeapNode* parent;

    BinomialHeapNode ()
    {
        this->pointerStore = NULL;
        this->resetNode();
    }

    void resetNode()
    {
        this->dataLoad = NULL;
        this->key = NULL;
        this->parent = NULL;
        this->degree = 0;
        this->child = NULL;
        this->sibling = this;
        this->setPointerStoreNULL();
        this->pointerStore = NULL;
    }

    BinomialHeapNode (T* data, unsigned int* keyPointer, BinomialHeapNode** pointerStore)
    {
        this->initializeNode(data, keyPointer, pointerStore);
    }

    void initializeNode(T* data, unsigned int* keyPointer, BinomialHeapNode** pointerStore)
    {
        this->dataLoad = data;
        this->key = keyPointer;
        this->parent = NULL;
        this->degree = 0;
        this->child = NULL;
        this->sibling = this;
        this->pointerStore = pointerStore;
        this->setPointerStore();
    }

    void setPointerStore()
    {
        if (this->pointerStore != NULL)
        {
            //cout<<"\nnode pointer value old: "<<*(this->pointerStore)<<" new: "<<this;
            *(this->pointerStore) = this;
        }
    }

    void setPointerStoreNULL()
    {
        if (this->pointerStore != NULL)
        {
            //cout<<"\nnode pointer value old: "<<*(this->pointerStore)<<" new: "<<NULL;
            *(this->pointerStore) = NULL;
        }
    }
};

template <class T>
class BinomialHeap
{
public:
    BinomialHeapNode<T>* head;

    BinomialHeap();
    ~BinomialHeap();
    BinomialHeapNode<T>* insert (T* data, unsigned int* keyPointer, BinomialHeapNode<T>** pointerStore);
    BinomialHeapNode<T>* insert (T* data, unsigned int* keyPointer);
    BinomialHeapNode<T>* getHead ();
    void meld (BinomialHeap<T>* node);
    T* removeMin();
    void decreaseKey(BinomialHeapNode<T>* node, unsigned int newKeyVal);
    void displayBFS ();
    int getNumberOfNodes();
    void emptyIt();

private:
    static const int maxNumberOfFreeNodes = 600;  //class constant
    BinomialHeapNode<T>** treeDeg;
    int numberOfNodes;
    int numOfFreeNodes;
    BinomialHeapNode<T>* freeNodes;

    BinomialHeapNode<T>* getFreeNode (T* data, unsigned int* keyPointer, BinomialHeapNode<T>** pointerStore);
    void releaseNode (BinomialHeapNode<T>* node);
    void meld (BinomialHeapNode<T>* node);
    BinomialHeapNode<T>* meld(BinomialHeapNode<T>* node, BinomialHeapNode<T>* node1);
    void pairwiseCombine ();
    void releaseHeap(BinomialHeapNode<T>* node);
};

template<class T>
void BinomialHeap<T>::releaseHeap(BinomialHeapNode<T>* node)
{
    BinomialHeapNode<T>* temp = node;
    while (node != NULL)
    {
        if (node->child != NULL)
        {
            this->releaseHeap(node->child);
        }
        temp = node;
        node = node->sibling;
        this->releaseNode(temp);
    }
}

template<class T>
void BinomialHeap<T>::emptyIt()
{
    BinomialHeapNode<T>* temp = NULL;
    this->releaseHeap(this->head);
    this->head = NULL;
    this->numberOfNodes = 0;
    //this->numOfFreeNodes = 600;
}

template <class T>
BinomialHeap<T>::~BinomialHeap()
{
    this->releaseHeap(this->head);
    //deleting all the nodes created
    BinomialHeapNode<T>* temp = this->freeNodes;
    while (temp != NULL)
    {
        BinomialHeapNode<T>* temp1 = temp;
        temp = temp->sibling;
        delete (temp1);
    }
    delete[] this->treeDeg;
}

template<class T>
BinomialHeapNode<T>* BinomialHeap<T>::getFreeNode(T* data, unsigned int* keyPointer, BinomialHeapNode<T>** pointerStore)
{
    if (this->freeNodes == NULL)
    {
        return NULL;
    }
    BinomialHeapNode<T>* temp = this->freeNodes;
    this->freeNodes = this->freeNodes->sibling;
    this->numOfFreeNodes--;
    temp->initializeNode(data, keyPointer, pointerStore);
    return temp;
}

template<class T>
void BinomialHeap<T>::releaseNode (BinomialHeapNode<T>* node)
{
    node->resetNode();
    node->sibling = this->freeNodes;
    this->freeNodes = node;
    this->numOfFreeNodes++;
}

//BFS
template<class T>
void BinomialHeap<T>::displayBFS()
{
    Queue<BinomialHeapNode<T> >* masterQueue = new Queue<BinomialHeapNode<T> >();
    Queue<BinomialHeapNode<T> >* slaveQueue = new Queue<BinomialHeapNode<T> >();
    if (this->head == NULL)
    {
        cout<<"\n\n<<<<Heap Empty!!!>>>>";
        return;
    }
    cout<<"\nHead is "<<*(this->head->key);
    slaveQueue->enqueue(this->getHead());
    int count = 0;
    BinomialHeapNode<T>* temp = NULL;
    cout<<endl<<"\nNumber of nodes in this heap: "<<this->numberOfNodes;
    do
    {
        delete (masterQueue);
        masterQueue = slaveQueue;
        slaveQueue = new Queue<BinomialHeapNode<T> >();
        cout<<endl<<endl<<"Level "<<count++<<"\t";
        while ((temp = masterQueue->dequeue()) != NULL)
        {
            //cout<<"\nMaster Dequeue: "<<*temp->key;
            int parentKey = (temp->parent != NULL) ? *(temp->parent->key) : 0;
            BinomialHeapNode<T>* temp1 = temp;
            do
            {
                cout<<"("<<parentKey<<", "<<*(temp1->key)<<")\t";
                if (temp1->child != NULL)
                {
                    //cout<<"\nSlave Enqueue: "<<*temp1->child->key;
                    slaveQueue->enqueue(temp1->child);
                }
                temp1 = temp1->sibling;
            } while (temp1 != temp);
        }
    } while (slaveQueue->hasElements());
}

template<class T>
void BinomialHeap<T>::decreaseKey(BinomialHeapNode<T>* node, unsigned int newKeyVal)
{
    //false condis
    if (node == NULL || newKeyVal > *(node->key))
    {
        return;
    }
    BinomialHeapNode<T>* temp = node;
    T* dataLoad = node->dataLoad;
    BinomialHeapNode<T>** pStore = node->pointerStore;
    unsigned int* key = node->key;
    while (temp->parent != NULL)
    {
        //found the correct position of the node
        if (*(temp->parent->key) < newKeyVal)
        {
            break;
        }
        temp->dataLoad = temp->parent->dataLoad;
        temp->key = temp->parent->key;
        temp->pointerStore = temp->parent->pointerStore;
        temp->setPointerStore();
        temp = temp->parent;
    }
    temp->dataLoad = dataLoad;
    temp->key = key;
    temp->pointerStore = pStore;
    temp->setPointerStore();

    //Reached top of tree and needs to update head pointer
    if (temp->parent == NULL && newKeyVal < *(this->head->key))
    {
        head = temp;
    }
    *(temp->key) = newKeyVal;   //update key
}

template<class T>
T* BinomialHeap<T>::removeMin()
{
    if (this->head == NULL)
    {
        //cout<<"remove fail";
        return NULL;
    }
    T* minData = head->dataLoad;
    //cout<<"\nminData: "<<minData->key1;
    BinomialHeapNode<T>* headChild = this->head->child;
    this->head->child = NULL;

    //Only node in the parent list
    if (this->head == this->head->sibling)
    {
        BinomialHeapNode<T>* temp = this->head;
        temp->setPointerStoreNULL();
        //delete (temp);
        this->releaseNode(temp);
        this->head = NULL;
    }
    else
    {
        BinomialHeapNode<T>* temp = this->head->sibling;
        BinomialHeapNode<T>* minTemp = this->head->sibling;
        while (temp->sibling != this->head)
        {
            if (*(minTemp->key) > *(temp->key))
            {
                minTemp = temp;
            }
            temp = temp->sibling;
        }
        temp->sibling = this->head->sibling;
        temp = this->head;
        this->head = minTemp;
        temp->sibling = temp;   //disconnect prev Head
        temp->setPointerStoreNULL();
        this->releaseNode(temp);
        //delete (temp);  // delete prev Head
    }
    if (headChild != NULL)
    {
        this->meld(headChild);  //remember to set parent of every top level nodes to NULL in pairwise combine
    }
    this->pairwiseCombine();
    this->numberOfNodes--;
    return minData;
}

template<class T>
void BinomialHeap<T>::pairwiseCombine ()
{
    //this->displayBFS();
    //Only 0/1 Binomial-Tree no need of pairwise Combine
    if (this->head == NULL)
    {
        return;
    }
    else if (this->head == this->head->sibling)
    {
        this->head->parent = NULL;
        return;
    }
    int n = (int)(log ((float)this->numberOfNodes)/log ((float)2)) + 2; //max degree can be ceil ( log (number of nodes)) + 1
    for (int i =0 ;i<n; i++)
    {
        treeDeg[i] = NULL;
    }

    BinomialHeapNode<T>* node = this->head->sibling;

    //adding first one to treedeg
    this->head->sibling = this->head;  //disconnecting from rest of the heap
    this->head->parent = NULL;  //top level list so should be NULL
    treeDeg[this->head->degree] = this->head;  //inserting first node into tree

    while (node != this->head)
    {
        BinomialHeapNode<T>* nextNode = node->sibling;	//storing next node for move

        node->sibling = node;   // disconnecting

        while (treeDeg[node->degree] != NULL)
        {
            BinomialHeapNode<T>* node1 = treeDeg[node->degree];
            treeDeg[node->degree] = NULL;   //removing it from the deg Array
            if (*(node1->key) < *(node->key))   //ensuring node has smaller value
            {
                BinomialHeapNode<T>* tNode = node1;
                node1 = node;
                node = tNode;
            }
            node->degree++;
            node->child = this->meld(node->child, node1);
            node1->parent = node;
            node->parent = NULL;
        }
        treeDeg[node->degree] = node;   //put it back into deg list
        node = nextNode;
    }
    BinomialHeapNode<T>* tempNode = NULL;
    BinomialHeapNode<T>* firstTempNode = NULL;
    for (int i=0; i<n; i++)
    {
        if (treeDeg[i] != NULL)
        {

            if (tempNode == NULL)
            {
                //cout<<"\nTree First i: "<<i;
                this->head = treeDeg[i];
                firstTempNode = treeDeg[i];
                tempNode = treeDeg[i];
                tempNode->parent = NULL;
            }
            else
            {
                if (*(this->head->key) > *(treeDeg[i]->key))
                {
                    this->head = treeDeg[i];
                }
                tempNode->sibling = treeDeg[i];
                tempNode = treeDeg[i];
                tempNode->parent = NULL;
            }
        }
    }
    tempNode->sibling = firstTempNode;
}

template<class T>
void BinomialHeap<T>::meld (BinomialHeap<T>* heap)
{
    if (heap == NULL)
    {
        return;
    }
    this->numberOfNodes += heap->numberOfNodes;
    this->meld(heap->getHead());
}

//in meld its expected to be a binomial heap so node will point to the min element of the next binomial heap
template<class T>
void BinomialHeap<T>::meld(BinomialHeapNode<T>* node)
{
    this->head = this->meld(this->head, node);
}

template<class T>
BinomialHeapNode<T>* BinomialHeap<T>::meld(BinomialHeapNode<T>* node, BinomialHeapNode<T>* node1)
{
    if (node == NULL || node1 == NULL)
    {
        if (node != NULL)
        {
            return node;
        }
        else if (node1 != NULL)
        {
            return node1;
        }
    }
    BinomialHeapNode<T>* nextNode1 = node1->sibling;
    BinomialHeapNode<T>* nextNode = node->sibling;
    node1->sibling = nextNode;
    node->sibling = nextNode1;
    if (*node->key < *node1->key)
    {
        return node;
    }
    return node1;
}

template<class T>
BinomialHeapNode<T>* BinomialHeap<T>::getHead()
{
    return this->head;
}

template<class T>
BinomialHeap<T>::BinomialHeap()
{
    this->head = NULL;
    this->numberOfNodes = 0;
    this->numOfFreeNodes = BinomialHeap::maxNumberOfFreeNodes;
    this->freeNodes = NULL;
    this->treeDeg = new BinomialHeapNode<T>*[BinomialHeap::maxNumberOfFreeNodes];
    for (int i=0; i < BinomialHeap::maxNumberOfFreeNodes-1; i++)
    {
        BinomialHeapNode<T>* temp = new BinomialHeapNode<T>();
        temp->sibling = this->freeNodes;
        this->freeNodes = temp;
    }
}

template<class T>
BinomialHeapNode<T>* BinomialHeap<T>::insert(T* data, unsigned int* keyPointer)
{
    return this->insert(data, keyPointer, NULL);
}

//Give in the data and key it will create a new node and meld
template<class T>
BinomialHeapNode<T>* BinomialHeap<T>::insert(T* data, unsigned int* keyPointer, BinomialHeapNode<T>** pointerStore)
{
    BinomialHeapNode<T>* node = this->getFreeNode(data, keyPointer, pointerStore);   //new BinomialHeapNode<T>(data, keyPointer, pointerStore);
    this->numberOfNodes++;
    this->meld (node);
    return node;
}

template<class T>
int BinomialHeap<T>::getNumberOfNodes()
{
    return this->numberOfNodes;
}


#endif
